#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int vis[100][100] = { 0 };
    int ret = 0;

    int m;
    int n;
    int cnt;
    int digit(int num)
    {
        int sum = 0;
        while (num)
        {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
    void dfs(int i, int j)
    {
        ++ret;
        vis[i][j] = true;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && digit(x) + digit(y) <= cnt && !vis[x][y])
                dfs(x, y);
        }
    }
    int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m;
        n = _n;
        cnt = _cnt;
        dfs(0, 0);
        return ret;
    }
};